using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.StrProblem
{
    //字符串问题的综合
    public class str
    {
        //将数组A的共同的字符列出来
        //eq:['qwe','qse','qae'] return:['q','e'].
        public List<String> commonChars(String[] A) {
            int[] minfreq = new int[26];
            Array.Fill(minfreq, int.MaxValue);
            foreach (String word in A) {
                int[] freq = new int[26];
                int length = word.Length;
                for (int i = 0; i < length; ++i) {
                    char ch = word[i];
                    ++freq[ch - 'a'];
                }
                for (int i = 0; i < 26; ++i) {
                    minfreq[i] = Math.Min(minfreq[i], freq[i]);
                }
            }

            List<String> ans = new List<String>();
            for (int i = 0; i < 26; ++i) {
                for (int j = 0; j < minfreq[i]; ++j) {
                    ans.Add(Convert.ToString((char) (i + 'a')) );
                }
            }
            return ans;
        }
        //763. 划分字母区间
        //字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，
        //同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
        //示例 1：
        //输入：S = "ababcbaca defegde hijhklij"
        //输出：[9,7,8]
        //        解释：
        //划分结果为 "ababcbaca", "defegde", "hijhklij"。
        //每个字母最多出现在一个片段中。
        //像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
        //提示：
        //S的长度在[1, 500] 之间。
        //S只包含小写字母 'a' 到 'z' 。
        public IList<int> PartitionLabels(string S)
        {
            List<int> result = new List<int>() ;
            Dictionary<char, int> map = new Dictionary<char, int>() ; //记录char c 和其最后出现位置的 map
            int start = 0, end = 0;
            for (int i = 0; i < S.Length; i++)
            {
                map[S[i]] = i;
            }
            for (int i = 0; i < S.Length; i++)
            {
                end = Math.Max(end, map[S[i]]);
                if (i == end)
                {
                    result.Add(end - start + 1);
                    start = i + 1;
                }
            }
            return result;
        }
    }
}